package arithmetic;
/* 希尔排序的主要思想先把所有数据进行分组小组内进行直接插入排序，
然后减少分组间隔再次进行直接插入排序，知道小组间距为1，然后整体进行直接插入排序，
因为在进行小组排序的同时已经把组内的顺序排好，当间距为1时，此时的数据已经是相当的有序，
在进行直接插入排序时，极大的减少了交换的次数，提高了效率*/
import java.lang.*;
import java .util.*;
public class Shell_sort {
    public static void main(String [] args)
    {
        Scanner in=new Scanner(System.in);
        int number;
        System.out.println("请输入要排序的个数:");
        number=in.nextInt();
        //直接插入排序
        int []a=new int [number];
        for(int i=0;i<number;i++)
        {
            a[i]=in.nextInt();
        }
        int gap = number;//得到数组的长度
        while ( gap > 1 )
        {
            gap = gap/3+1;//设计间隔长度 +1 保证最后gap等一
            //单趟排序 每个区间里面进行插入排序
            for(int i = 0;i < number-gap; ++i)
            {
                int end = i;
                int tmp = a[end+gap];//设定中间值 便于后面比较与赋值
                while( end >= 0 && a[end] > tmp )//循环条件设立
                {
                    a[end+gap] = a[end];
                    end -= gap;
                }
                a[end+gap] = tmp;
            }
        }
        //希尔排序完之后对所得到的新的数组进行插入排序
        for(int i =1;i < a.length; ++i)//用end的位置控制边界
        {
            //单趟排序
            int end = i - 1 ;//下标减1 便于前面排好的数据与下标为i的数据进行比较
            int tmp = a[i];//设定中间变量储存值 便于后面插入
            while( end >= 0 )//循环继续条件
            {
                if( a[end] > tmp )
                {
                    a[end+1] = a[end];//将大的数据放到后面
                    end--;
                }
                else
                    break;
            }
            a[end+1] = tmp;//插入数据数据或者保持不变
        }
        for(int element :a)
        {
            System.out.println(element);
        }
    }
}
